#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <string.h>

#define LEN 32 

void print(int *, int);

void insertion_sort_n (int * a, int n)
{
    int i;
    int j;
    int v;

    for (i = 1; i < n; i++) {
	v = a[i];
	                          // failed here!
//	for (j = i - 1; j >= 0 && a[j] > a[j+1]; j--)
	for (j = i - 1; j >= 0 && a[j] > v; j--)
//	    if (a[j] > a[j+1])  // also failed here!
		a[j+1] = a[j];
	a[j+1] = v;
    }
}

int find_min (int * a, int p, int q)
{
#if 1
    if (!a || p < 0 || q < 0 || p > q)
	return -1;
#endif
    int min_v; 
    int min_i;
    int i;

    min_v = 0x7fffffff;
    min_i = -1;
    for (i = p; i <= q; i++)
       if (a[i] < min_v) {
	   min_v = a[i];
	   min_i = i;
       }

    return min_i;
}

void swap (int * a, int p, int q)
{
    // NOTE: will fail if p = q, add a check
    if (p >= 0 && q >=0 && p < q) {
	a[p] = a[p] + a[q];
	a[q] = a[p] - a[q];
	a[p] = a[p] - a[q];
    }
#if 0
    int tmp;
    tmp = a[p];
    a[p] = a[q];
    a[q] = tmp;
#endif
}

void selection_sort_n (int * a, int n)
{
    int i;
    int j;

    for (i = 0; i < n - 1; i++) {
	j = find_min(a, i, n-1);
	//printf("min: %d, %d\n", j, a[j]);
	swap (a, i, j);
	//print(a, LEN);
    }
}

void print(int * a, int n)
{
    int i;

    printf("array[%d]: ", n);
    for (i = 0; i < n; i++)
	printf("%d\t", a[i]);
    printf("\n\n");
}

void merge(int * a, int p, int q, int r)
{
    int i, j, k;
    int l, l1, l2;
    int * a1, * a2; 

    l1 = q - p + 1;
    l2 = r - q;
    a1 = (int*)malloc(sizeof(int) * (l1 + 1));
    a2 = (int*)malloc(sizeof(int) * (l2 + 1));

    for (i = 0; i < l1; i++)
	a1[i] = a[p+i];
    a1[i] = 0x7fffffff;	// sentinel
    for (i = 0; i < l2; i++)
	a2[i] = a[q+1+i];
    a2[i] = 0x7fffffff;

    l = l1 + l2;	// assure the end of while loop
#if 0
    k = 0, i = 0, j = 0;
    while (k < l) {
	if (a1[i] <= a2[j])
	    a[p + k++] = a1[i++];
	else 
	    a[p	+ k++] = a2[j++]; 
    }
#endif
    for (k = p, i = 0, j = 0; k <= r; k++)
	if (a1[i] <= a2[j])
	    a[k] = a1[i++];
	else
	    a[k] = a2[j++];

    free(a1);
    free(a2);
}

void merge_sort(int * a, int p, int r)
{
    int q;

    if (p < r) {
	q = (p + r)/2;
	merge_sort(a, p, q);
	merge_sort(a, q+1, r);
	merge(a,p,q,r);
    }
}

int binary_search(int * a, int v, int p, int r)
{
    int m;

    if (p <= r) {
	m = (p + r) / 2;
	if (a[m] == v)
	    return m;
	else if (a[m] > v)
	    return binary_search(a, v, p, m - 1);
	else
	    return binary_search(a, v, m + 1, r);

    }

    return -1;
}

int checksum (int * a, int x, int n)
{
    int i;
    int pos;

    for (i = 0; i < n; i ++) {
	// pos = binary_search(a, x - a[i], 0, n - 1); 
	// should exclude the have-checked element from the current check
	pos = binary_search(a, x - a[i], i, n - 1); 
	if (pos != -1 && pos != i) {
	    printf("checksum ok: %d(a[%d]) + %d(a[%d]) = %d\n", a[i], i, a[pos], pos, x);
	    return ~0L;
	}
    }
    return 0;
}

#if 1
int main(int argc, char *argv[])
{
    int i;
    int iLen, iLoop, *a, *b;
    int v;
    time_t ttStart, ttEnd;

    if (argc < 3) {
	printf("usage: %s looptime len.\n", argv[0]);
	exit(1);
    }
    iLoop = atoi(argv[1]);
    iLen = atoi(argv[2]);
    printf("loop: %d, sort len: %d\n", iLoop, iLen); 
    a = (int *)malloc(sizeof(int) * iLen);
    b = (int *)malloc(sizeof(int) * iLen);
    if (! a || ! b) {
	printf("no more mem!\n");
	exit(2);
    }

    srand((long)time(NULL));
    for (i = 0; i < iLen; i++)
	a[i] = rand() % 100;
    memcpy(b, a, sizeof(int) * iLen);
//    print(a, sizeof(a) / sizeof(a[0]));

//    insertion_sort_n (a, sizeof(a) / sizeof(a[0]));
//    selection_sort_n(a, sizeof(a) / sizeof(a[0]));

    ttStart = time(NULL);
    for (i = 0; i < iLoop; i++) {
	//if (i == iLoop / 2) print(a, iLen);
	merge_sort(a, 0, iLen - 1);
	//if (i == iLoop / 2) print(a, iLen);
    	memcpy(a, b, sizeof(int) * iLen);
    }
    ttEnd = time(NULL);
    printf("merge_sort time: start %u, end %u, %u\n", ttStart, ttEnd, ttEnd - ttStart);

    ttStart = time(NULL);
    for (i = 0; i < iLoop; i++) {
	// if (i == iLoop / 2) print(a, iLen);
	insertion_sort_n(a, iLen);
	//if (i == iLoop / 2) print(a, iLen);
    	memcpy(a, b, sizeof(int) * iLen);
    }
    ttEnd = time(NULL);
    printf("insertion_sort_n time: start %u, end %u, %u\n\n", ttStart, ttEnd, ttEnd - ttStart);


//    print(a, sizeof(a) / sizeof(a[0]));
    
#if 0
    v = rand() % 100;
    //v = a[0] * 2;
    printf("value is %d\n", v);
#if 0
    if (binary_search(a, v, 0, sizeof(a) / sizeof(a[0]) - 1) != -1)
	printf("%d hit\n", v);
    else
	printf("%d lost\n", v);
#endif
    checksum(a, v, sizeof(a) / sizeof(a[0]));
#endif
    free(a);
    free(b);

    return 0;
}
#endif

#if 0
int main()
{

}
#endif

#if 0
int main()
{
    printf("hello, world\n");

    return 0;
}
#endif
